#!/usr/bin/env python
#-*- coding: utf-8 -*-
#__author__:vincentlc
#time: 16/4/4 : 00:51

'''
You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
'''


class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0 or n == 1:
          return 1
        pre = 1
        current = 1
        i = 2
        while i <= n:
            temp = current + pre
            pre = current
            current = temp
            i+=1
        return current

    def climbStairs2(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 0:
            return 0
        if n <= 1:
            return 1
        return self.climbStairs2(n - 1) + self.climbStairs2(n - 2)

    def fibon(self,n):
        a = b = 1
        for i in range(n):
            yield a
        a, b = b, a + b

a =Solution()
print (a.climbStairs(1))
print (a.climbStairs(2))
print (a.climbStairs(35))


print(a.fibon(1))
print(a.fibon(2))
# for i in a.fibon(35):
#     print (i)

